// https://www.lintcode.com/problem/longest-common-subsequence/description

class Solution {
public:
    /**
     * @param A: A string
     * @param B: A string
     * @return: The length of longest common subsequence of A and B
     */
    int longestCommonSubsequence(string &A, string &B) {
// Input
// ""
// ""
// Expected
// 0
        if (A.empty() || B.empty()) return 0;    
        int m = A.length() + 1;
        int n = B.length() + 1;
        vector<vector<int>> record_vec(m, vector<int>(n, 0));
        for (int i = 0; i < m; ++i)
        {
            record_vec[i][0] = 0;            
        }
        for (int j = 0; j < n; ++j)
        {
            record_vec[0][j] = 0;
        }
        for (int i = 1; i < m; ++i)
        {
            for (int j = 1; j < n; ++j)
            {
                if (A[i - 1] == B[j - 1]) record_vec[i][j] = record_vec[i - 1][j - 1] + 1;
                record_vec[i][j] = max(max(record_vec[i][j - 1], record_vec[i - 1][j]), record_vec[i][j]);
            }
        }
        return record_vec[m - 1][n - 1];
    }
};